COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\\M1BASL30\M2BASB30\M3NGR25\M4NGR20\F2\CSTANFORD UNIVERSITY
C00014 ENDMK
C⊗;
\\M1BASL30;\M2BASB30;\M3NGR25;\M4NGR20;\F2\CSTANFORD UNIVERSITY
\F3\CSTANFORD, CALIFORNIA 94305
\F4COMPUTER SCIENCE DEPARTMENT\←L\-R\/'7;\+R\→.\→S   Telephone:
\←S\→.415-497-4971
\F1\CJuly 11,1975



Mr. Ken Bowman
College Division
McGraw-Hill Publishing Co.
1221 Avenue of the Americas
New York, N.Y. 10020


Dear Mr. Bowman:

\JThis letter will hopefully clarify some of our discussion about the
market and potential of my LISP manuscript: The Anatomy of the language LISP
 (tentative title).
I should note that the following discussion reflects the structure of the final
text rather than the current manuscript. Most of the discrepancies involve
reorganization, rather than major modifications.

In its  most obvious application the book represents the best discussion of
all aspects of the LISP language. The text covers the programming aspects,
introducing structured programming through the use of McCarthy's abstract syntax
as it  develops the techniques of recursive programming.
LISP's list notation is introduced as a discussion of abstract data structures
and the problems of representation.
The use of abstract algorithms and data structures is an excellent way to
explain the true intent of  structured programming; this approach will be
strengthened in the next draft.

After the student has gained familiarity with the basic properties of the language
we introduce an abstract version of the  LISP interpreter. This interpreter
clearly demonstrates the power of abstraction and refinement in programming.
The student is also given a precise description of the meaning of LISP constructs.
The discussion of this LISP interpreter is also quite helpful in giving 
insights into the problematic areas of binding strategies.

Though the interpreter is an accurate description of LISP's semantics, the
level of description is higher than what one usually expects as a implementation.
We remedy this next, beginning a detailed description of a typical LISP implementation.
This is done in two phases: first, the static structure is described. This
covers the storage conventions for Symbolic Expressions, the LISP primitives,
the storage management facilities, and two common strategies for maintaining
variable bindings. This section gives motivation for many of the typical algorithms
and data representation which are currently studied in data structures courses.
My past experience (teaching at UCLA, UC Santa Cruz, Stanford, and San Jose State)
has been that motivation is weak in many current texts.

The second phase of LISP implementation covers the dynamic structure of LISP:
how recursion is implemented, how environments are maintained, how running
and debugging in LISP (or indeed any good on-line language) is usually done. 
This section also discusses compilation
and gives abstract compilers for various subsets of LISP. Since
the student understands the structure of the LISP interpreter, the compiling
algorithms are easily assimilated now.
The purpose and structure of compilers is most lucidly demonstrated by
seeing a compilation algorithm expressed in LISP. Once students understand
the basic algorithms they typically are able to extend them to larger
languages or improve them for more efficient code. This section also
covers one-pass assemblers, bootstrapping, and will soon do more with code
optimization.

The section on "Storage Structures and Efficiency" begins a more typical
discussion of data structures, but uses the intuitions gained in the prior
sections to motivate the study of vectors, arrays and string processors.
 This section also
introduces several of LISP's pointer manipulation operations as devices to
improve efficiency. 

The style of the text is from the abstract
to the concrete. The early sections deal in abstract algorithms and data
structures. The notation is mathematical and high-level. This gives a very
concise way of expressing complex algorithms. As the lower level representations
are specified the algorithm becomes bulkier but not more difficult to 
understand. Thus the abstract LISP interpreter is quite understandable
independent of how it will be coded for a specific machine. Later, as we
map LISP onto a typical machine, the level of detail will increase but
by that time the student will already understand the interpreter as a LISP
algorithm. The section on "Storage Structures and Efficiency" is even more
concrete, analyzing alternative ways of storing data and studying several
algorithms which can improve efficiency through pointer manipulation.

The final section on the "Implications of LISP" will discuss a variety of
topics under two basic headings.
First, the practical implications to language design;
after such a complete analysis of LISP, we are able to see many weaknesses
both in LISP and in several more recent endeavors. We discuss the
the lessons that can be learned from fifteen years of experience with LISP.
The second topic involves LISP and its
theoretical implications in the mathematical theory of computation.
McCarthy's work on LISP was one of the first attempts to bring a mathematical
rigor to programming. What we will do here is relate the more traditional
studies  of mathematical logic and recursion theory to computer science.
This will involve a careful analysis of the three ideas of computation,
deduction, and truth. This relates LISP to the recent work of D. Scott,
C. Wadsworth, and M. Gordon. Some of this material is in the current manuscript
but spread out and in very poor shape. I have been teaching a graduate seminar
this summer on just this subject so revision and incorporation will be
minor.

Judging from the reaction to the text, both in the research community and
from students I believe, the text will sell very well. To my knowledge
there is currently no text which covers the broad range of topics in such a unified
manner. Students of mine who have gone on to more advanced work have 
commented on the benefits of having a clear understanding of the relationships
between various aspects of the field. Indeed I feel that there is a  premature
fragmenting or departmentalization of computer science. This text is an attempt
to reverse that trend.

Besides its immediate applications as a text, the approach to programming
and data structures which is presented is the basis of a proposal for
an interactive programming environment. This proposal, submitted to NSF,
will develop on-line programming methods to aid  in the construction of
correct and reliable software through the use of abstraction and refinement
techniques. The results of this proposal should enhance the saleability
of the book.

I hope this outline will help clarify the structure and purpose of the book.
I am currently revising the text and am most anxious to conclude these
contractual matters. 
\.
\←L\→S\←R\-L\/'2;\+L\→L

Yours sincerely,



John R. Allen
Research Associate
Computer Science Dept
Artificial Intelligence Lab

\←S\→L